1. Field of Inventions
The instant inventions relate to computer system memory, and the instant inventions more particularly relates to indexing computer system memory.
2. Discussion of Related Art
Computer systems typically store data in large main memory structures. Data may include any information capable of being stored, including machine instructions, application information, etc. These large memory structures have large latencies that can be many orders of magnitude longer than the time used for each processing cycle of a processor. Such large latencies may present a detriment to high performance processing.
To address the large latencies associated with large main memory structures, modern computer systems include one or more caches separating processors from the large main memory structures. The caches serve to amortize costly accesses to the large main memory structures, and improve access to data by locating frequently used data closer to the processors.
Typically, when data is needed by a processor, a cache searches its contents for a memory address of the needed data. This may be achieved by referencing a portion of the memory address of the data in the large main memory structure to index the cache. Such a portion typically includes a set of low-order bits of the address. The remainder of the address is used as a tag to determine if the referenced location in the cache matches the originally referenced memory location in the large main memory structure.
When an address is found in a cache, it is known as a “cache hit.” Upon such an event, the data in the cache location is forwarded to the processor. When an address is not found in the cache, it is known as a “cache miss.” In the event of a cache miss, the cache forwards the address to either another higher level cache or the large main memory structure. When the request is finally serviced, the cache may update its contents and overwrite previously cached data to store the newly needed data.
The mapping of an address in main memory to a location in a cache is a matter performed in accordance with an indexing function. In common cache designs, a referenced address A is mapped to a location in a cache using the indexing function h(A)=A mod S, where S equals the number of available locations in the cache. This indexing function is known as bit selection. Bit selection is not a perfect indexing function, however, in that two or more addresses may map into the same location, resulting in a cache conflict. This is a common phenomenon in real world applications because caches may be significantly smaller than the space of addresses that a processor can reference (e.g., any location in a large main memory structure). If a sequence of conflicting addresses is encountered, the cache may become less effective as referenced data compete for the same location in the cache.
The performance of modern processors is severely dependent on the performance of their supporting caches. Cache misses that result from competition for the limited data locations in a cache plague typical cache architectures. A common solution to such cache misses is to increase the associativity of the cache. Associativity of a cache refers to a characteristic of a cache to allow a single referenced memory address of the main memory structure to be placed in more than a single location in the cache, as is known in the art. While this strategy may be effective, it comes with significant costs in terms of design complexity. Furthermore, this strategy continues to rely on a cache indexing function that may produce the cache misses in the first place. An ineffective cache indexing function, for example, may continue to cause misses despite associativity because of local hot and cold spots, leaving much of the cache underutilized and much of the cache overutilized.
Certain embodiments of the instant inventions may address or alleviate one or more of the above issues, but other embodiments may not address these specific issues in the prior art and the above discussion is not intended to be limiting.